﻿using System;

namespace Algorithms.DataStructures
{
    /* We shouldn't rely on _values.Length, because this algorithm does not always
     * use all items in this array.
     * Use HeapSize and private LastIndex properties
     */
    public class MaxBinaryHeap
    {
        private int[] _values;
        public int HeapSize
        {
            get { return LastIndex+1; }
        }

        private int LastIndex { get; set; }

        public MaxBinaryHeap()
        {
            _values=new int[0];
            LastIndex = -1;
        }

        public MaxBinaryHeap(int[] arr)
        {
            _values=new int[arr.Length];
            Array.Copy(arr,_values,arr.Length);
            LastIndex = _values.Length - 1;
            int middleIndex = LastIndex/2;
            Array.Copy(arr,_values,arr.Length);
            for (int i = middleIndex; i >= 0; --i)
            {
                BalanceHeap(i);
            }
        }

        public int ExtractFromHead()
        {
            if (HeapSize == 0)
                throw new InvalidOperationException();
            int elem = _values[0];
            AdditionalFunctions.Swap(ref _values[LastIndex], ref _values[0]);
            --LastIndex;
            BalanceHeap(0);
            return elem;
        }

        public void AddItem(int item)
        {
            if (LastIndex==_values.Length-1)
                Array.Resize(ref _values, _values.Length*2+1);
            _values[++LastIndex] = item;
            int currentIndex = LastIndex;
            int parentIndex = ((currentIndex - 1)/2);
            while (parentIndex >= 0 && _values[parentIndex] < _values[currentIndex])
            {
                AdditionalFunctions.Swap(ref _values[parentIndex], ref _values[currentIndex]);
                currentIndex = parentIndex;
                parentIndex = ((currentIndex - 1)/2);
            }
        }

        //This function modifies heap (cleans it).
        public void AddHeap(MaxBinaryHeap heap)
        {
            while (heap.HeapSize > 0)
            {
                int newElement = heap.ExtractFromHead();
                AddItem(newElement);
            }
        }

        public bool HeapIsBalanced()
        {
            int middleIndex = LastIndex / 2;
            for (int i = 0; i <= middleIndex; ++i)
            {
                int leftChildIndex = i*2 + 1;
                int rightChildIndex = i * 2 + 2;

                if (leftChildIndex <= LastIndex && _values[i] < _values[leftChildIndex])
                    return false;

                if (rightChildIndex <= LastIndex && _values[i] < _values[rightChildIndex])
                    return false;
            }
            return true;
        }

        private void BalanceHeap(int index)
        {
            if (index >LastIndex)
                return;
            int leftChildIndex = index*2 + 1;
            int rightChildIndex = index * 2 + 2;
            int maxValueIndex = index;

            if (leftChildIndex <= LastIndex && _values[maxValueIndex] < _values[leftChildIndex])
                maxValueIndex = leftChildIndex;

            if (rightChildIndex <= LastIndex && _values[maxValueIndex] < _values[rightChildIndex])
                maxValueIndex = rightChildIndex;

            if (maxValueIndex == index)
                return;

            AdditionalFunctions.Swap(ref _values[index], ref _values[maxValueIndex]);
            BalanceHeap(maxValueIndex);
        }

    }
}
